A network may comprise a number of network nodes communicating information in accordance with one or more communication protocols. One such protocol is the Internet Protocol (IP). When one IP network node has a large amount of data to send to another IP network node, the data may be transmitted as a series of packets referred to as IP datagrams. It is usually preferable that the datagrams be of the largest size that does not require fragmentation anywhere along the path from the source to the destination. This datagram size is referred to as the Path MTU (PMTU), and it is equal to the minimum of the MTUs of each hop in the path. Conventional techniques for a network node to discover a PMTU for an arbitrary path may be relatively slow. Consequently, there may be need for improvements in such techniques to improve PMTU discovery in a network.